#ifndef _SEARCH_H_
#define _SEARCH_H_

#ifndef INT_MAX
#define INT_MAX 2147483647
#define INT_MAX_DEFINED true
#endif

template <class T>
int  LinearSearch(T *a, T b, int n){
	for(int i = 0 ; i < n; i++)
		if(a[i] == b)
			return i;
	return -1;
}

template <class T>
int BinarySearch(T *a, T b, int n){
	first = 0;
	last = n - 1;
	middle = (first+last)/2;
 
	while( first <= last )
	{
		if ( array[middle] < b )
			first = middle + 1;    
		else if ( array[middle] == b ) 
			return middle;
		else
			last = middle - 1;
		middle = (first + last)/2;
	}
	if ( first > last )
		return -1;
}

template <class T>
int FibimacciSearch(const T *arr, T val, int n)
{
int k, idx, offs;
static int prevn=-1, prevk=-1;
const static int Fib[48]={0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765,
             10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578,
             5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296,
			 433494437, 701408733, 1134903170, 1836311903, INT_MAX};
  if(n!=prevn){
	  k=(n>1)? BinarySearch(Fib, sizeof(Fib)/sizeof(int), n) : 1;
    prevk=k;
    prevn=n;
  }
  else k=prevk;
  for(offs=0; k>0;  ){
    idx=offs+Fib[--k];
    if(idx>=n || val<arr[idx]) 
		continue;
    else if (val>arr[idx]){
      offs=idx;
      --k;
    }
    else
      return idx;
  }
  return -1;
}

#if INT_MAX_DEFINED
#undef INT_MAX
#undef INT_MAX_DEFINED
#endif


#endif